package zuo.algo.c12;

import zuo.algo.util.StringUtils;

import java.util.Random;

/**
 * 01:28-KMP
 */
public class Kmp {

    public static int getIndexOf(String str1, String str2) {
        if (str1 == null || str2 == null || str1.length() < str2.length()) {
            return -1;
        }
        // 为了兼容Java的String.indexOf方法
        if (str2.length() < 1) {
            return 0;
        }
        int[] next = getNextArr(str2);
        int idx1 = 0, idx2 = 0;
        int len1 = str1.length(), len2 = str2.length();
        while (idx1 < len1 && idx2 < len2) {
            if (str1.charAt(idx1) == str2.charAt(idx2)) {
                idx1++;
                idx2++;
            } else if (next[idx2] == -1) {
                // next[idx2] == -1 等同于 idx2 == 0
                idx1++;
            } else {
                idx2 = next[idx2];
            }
        }
        return idx2 == len2 ? idx1 - idx2 : -1;
    }

    private static int[] getNextArr(String str2) {
        int len = str2.length();
        if (len <= 1) {
            return new int[] {-1};
        }
        int[] next = new int[len];
        next[0] = -1;
        next[1] = 0;
        int idx = 2;
        int val = 0;
        while (idx < len) {
            if (str2.charAt(val) == str2.charAt(idx - 1)) {
                next[idx++] = ++val;
            } else if (val == 0) {
                next[idx++] = 0;
            } else {
                val = next[val];
            }
        }
        return next;
    }

    public static void main(String[] args) {
        String str1 = "ooog";
        String str2 = "oog";
        int idx = getIndexOf(str1, str2);
        System.out.println(idx);
        Random random = new Random();
        for (int i = 0; i < 10000000; i++) {
            int len = random.nextInt(100);
            str1 = StringUtils.getRandomStr(100 * len);
            str2 = StringUtils.getRandomStr(len);
            int idx1 = str1.indexOf(str2);
            int idx2 = getIndexOf(str1, str2);
            if (idx1 != idx2) {
                System.out.println("idx1:" + idx1 + " str1:" + str1);
                System.out.println("idx2:" + idx2 + " str2:" + str2);
                throw new RuntimeException();
            }
            System.out.println("idx1=" + idx1 + " idx2=" + idx2 + " " + i);
        }
    }
}
